{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第六章：构建 C++ 撮合引擎\n",
    "\n",
    "上一章我们讨论了将在本书中实现的电子交易生态系统的整体设计。本章将从交易所侧的撮合引擎入手作为第一个组件。我们将专注于根据客户端提交的订单，构建交易所撮合引擎的订单簿；实现用于追踪这些订单、在订单交叉时进行撮合、并更新订单簿所需的各种数据结构与算法。所谓“交叉”，是指买单价格大于或等于卖单价格时，双方可以互相成交——我们将在本章中更详细地说明这一点。我们的目标是在这些操作中尽可能降低延迟，因为基础设施最快的交易所通常能吸引更多业务、也更受市场参与者青睐。暂时我们不会涉及交易所中的行情发布器与订单网关服务器组件。\n",
    "\n",
    "本章将涵盖以下主题：\n",
    "\n",
    "- 定义撮合引擎中的操作与交互\n",
    "- 构建撮合引擎与外部数据交换\n",
    "- 构建订单簿并撮合订单\n",
    "\n",
    "首先，我们会阐明一些简化撮合引擎的假设，以限定本书讨论的范围；随后在首个小节中定义若干类型、常量以及基础结构。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 在撮合引擎中定义操作与交互 / Defining the operations and interactions in our matching engine\n",
    "\n",
    "Here, we will declare and define the types, constants, and structures we will need as we build the matching engine in this chapter.\n",
    "\n",
    "本节将声明并定义我们在本章构建撮合引擎时所需的类型、常量与结构。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 定义若干类型与常量 / Defining some types and constants\n",
    "\n",
    "Let us define a few common typedefs to document the types we will use in the rest of this book. We will also define some constants to represent some assumptions that exist, purely for the purpose of simplifying the design of our matching engine. Note that you don’t need these limits/constants, and we leave this enhancement up to the interested among you. All the code for this subsection can be found in the Chapter6/common/types.h file in the GitHub repository for this book.\n",
    "\n",
    "我们先透过一些常见的 `typedef` 来说明本书后续将使用的类型，同时定义若干常量，用来表达为了简化撮合引擎设计而作出的假设。请注意，这些限制或常量并非必须，感兴趣的读者可以自行扩展。本小节的全部代码可在本书配套 GitHub 仓库的 [`Chapter6/common/types.h`](./common/types.h) 文件中找到。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 若干基础类型 / Defining a few basic types\n",
    "\n",
    "We will define some types to hold different attributes in our electronic trading system, such as the following:\n",
    "• OrderId to identify orders\n",
    "• TickerId to identify trading instruments\n",
    "• ClientId for the exchange to identify different clients\n",
    "• Price to hold prices for instruments\n",
    "• Qty to hold quantity values for orders\n",
    "• Priority to capture the position of an order in the First In First Out (FIFO) queue at a price level, as discussed in the Designing Our Trading Ecosystem chapter.\n",
    "• Side to signify the side (buy/sell) of an order\n",
    "\n",
    "We will also provide basic methods to convert these to strings purely for logging purposes. Let us look at each one of these code blocks to understand the declarations next:\n",
    "\n",
    "我们会定义用于在电子交易系统中保存不同属性的类型，例如：\n",
    "\n",
    "- `OrderId`：用于标识订单\n",
    "- `TickerId`：用于标识交易标的\n",
    "- `ClientId`：便于交易所区分不同客户\n",
    "- `Price`：用于记录标的价格\n",
    "- `Qty`：用于记录订单数量\n",
    "- `Priority`：用于表示订单在某个价位 FIFO 队列中的排位（参见《设计我们的交易生态系统》一章）\n",
    "- `Side`：用于表示订单方向（买/卖）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们还会提供将这些类型转换为字符串的基础方法，主要用于日志。以下逐段说明这些声明：\n",
    "\n",
    "首先定义 `OrderId` 类型（`uint64_t`），以及用于日志输出的 `orderIdToString()` 方法。我们还添加一个 `OrderId_INVALID` 哨兵值，用于表示无效订单：\n",
    "\n",
    "- [`OrderId`](./common/types.h#L18)\n",
    "\n",
    "`TickerId` 类型用于标识交易标的，本质上是 `uint32_t`，并提供 `tickerIdToString()` 方法及 `TickerId_INVALID` 哨兵值：\n",
    "\n",
    "- [`TickerId`](./common/types.h#L29)\n",
    "\n",
    "`ClientId` 用于区分不同的交易参与者。`ClientId_INVALID` 表示无效值，`clientIdToString()` 用于日志输出：\n",
    "\n",
    "- [`ClientId`](./common/types.h#L40)\n",
    "\n",
    "接下来是 `Price` 类型，用于记录订单价格。我们定义 `Price_INVALID` 来表示无效价格，并提供 `priceToString()` 方法：\n",
    "\n",
    "- [`Price`](./common/types.h#L51)\n",
    "\n",
    "`Qty` 是 `uint32_t` 类型，用于表示订单数量，同样提供 `Qty_INVALID` 哨兵值与 `qtyToString()` 方法：\n",
    "\n",
    "- [`Qty`](./common/types.h#L62)\n",
    "\n",
    "`Priority` 表示订单在队列中的排位，类型为 `uint64_t`，带有 `Priority_INVALID` 哨兵值及 `priorityToString()` 方法：\n",
    "\n",
    "- [`Priority`](./common/types.h#L73)\n",
    "\n",
    "`Side` 是一个枚举，包含两个有效值，并提供 `sideToString()` 方法，如下所示：\n",
    "\n",
    "- [`Side`](./common/types.h#L84)\n",
    "\n",
    "以上便是本章所需的基础类型。接下来，我们将定义一些限制，以简化系统设计。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 定义若干限制与约束 / Defining some limits and constraints\n",
    "\n",
    "我们为撮合引擎设置了一组常量，用于描述在实现时采用的简化假设：\n",
    "\n",
    "- `LOG_QUEUE_SIZE`：日志模块使用的无锁队列容量，表示在队列写满前最大可缓存的字符数量。\n",
    "- `ME_MAX_TICKERS`：交易所支持的交易标的数量上限。\n",
    "- `ME_MAX_CLIENT_UPDATES`：撮合引擎尚未处理的全部客户端订单请求数上限，也对应订单服务器尚未发布的撮合回应数上限。\n",
    "- `ME_MAX_MARKET_UPDATES`：撮合引擎已生成但尚未由行情发布器发送的市场更新数量上限。\n",
    "- `ME_MAX_NUM_CLIENTS`：我们的交易生态系统中可同时存在的市场参与者数量上限。\n",
    "- `ME_MAX_ORDER_IDS`：单个交易标的允许存在的订单数量上限。\n",
    "- `ME_MAX_PRICE_LEVELS`：撮合引擎维护的限价订单簿价格层级深度上限。\n",
    "\n",
    "这些数值纯属示例，可根据部署环境的系统容量随意调整。之所以选取 2 的幂，仅是为了在地址计算时可以使用位移操作，但在现代处理器上收益极小，无需刻意追求。相关常量的代码如下：\n",
    "\n",
    "- [`LOG_QUEUE_SIZE`](./common/logging.h#L13)\n",
    "- [`ME_MAX_TICKERS`](./common/types.h#L9)\n",
    "\n",
    "目前我们所需的常量就这些。接下来，可以把注意力转移到撮合引擎内部需要的更复杂数据结构上。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 设计撮合引擎 / Designing the matching engine\n",
    "\n",
    "撮合引擎需要若干数据结构，以便与行情发布器和订单服务器进行通信。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 定义 MEClientRequest 与 ClientRequestLFQueue / Defining the MEClientRequest and ClientRequestLFQueue types\n",
    "\n",
    "`MEClientRequest` 结构由订单服务器使用，用来把客户端的订单请求转发给撮合引擎。回忆一下，订单服务器与撮合引擎之间通过我们之前实现的无锁队列通信。`ClientRequestLFQueue` 是 `MEClientRequest` 对象的无锁队列类型别名。完整代码位于本书 GitHub 仓库的 `Chapter6/order_server/client_request.h`。\n",
    "\n",
    "这里要注意两点：\n",
    "\n",
    "1. 使用 `#pragma pack()` 指令确保这些结构体紧凑无填充。这很重要，因为它们在后续章节会作为扁平二进制结构在网络上传输。\n",
    "2. 定义 `ClientRequestType` 枚举，用于标识订单请求的类型（新订单或撤单），同时提供 `INVALID` 哨兵值与 `clientRequestTypeToString()` 转换函数。\n",
    "\n",
    "- [`#pragma pack()`](./order_server/client_request.h#L11)\n",
    "- [`ClientRequestType`](./order_server/client_request.h#L12)\n",
    "\n",
    "随后定义 `MEClientRequest` 结构，用于承载交易参与者发送给交易所的单笔请求。注意，这只是撮合引擎内部的表示形式，未必与客户端发送的外部格式一致；后者将在下一章《与市场参与者通信》中介绍。结构中包含以下成员：\n",
    "\n",
    "- `type_`：请求类型（`ClientRequestType`）\n",
    "- `client_id_`：请求所属客户端（`ClientId`）\n",
    "- `ticker_id_`：目标交易标的（`TickerId`）\n",
    "- `order_id_`：相关订单 ID（新单或已有订单标识）\n",
    "- `side_`：订单方向（`Side`）\n",
    "- `price_`：订单价格（`Price`）\n",
    "- `qty_`：订单数量（`Qty`）\n",
    "\n",
    "同时提供 `toString()` 方法，方便后续日志输出：\n",
    "\n",
    "- [`MEClientRequest`](./order_server/client_request.h#L30)\n",
    "\n",
    "最后，定义 `ClientRequestLFQueue` 为上述结构的无锁队列类型别名，并通过 `#pragma pack(pop)` 恢复默认对齐设置（我们只希望紧凑排列会被网络传输的结构体）：\n",
    "\n",
    "- [`ClientRequestLFQueue`](./order_server/client_request.h#L59)\n",
    "\n",
    "接下来，我们将定义撮合引擎用于向订单服务器发送订单响应的结构。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 定义 `MEClientResponse` 与 `ClientResponseLFQueue`\n",
    "\n",
    "撮合引擎需要向订单服务器回报订单状态，因此我们定义 `MEClientResponse` 结构及其无锁队列别名 `ClientResponseLFQueue`。相关代码位于 [`Chapter6/order_server/client_response.h`](./order_server/client_response.h)。\n",
    "\n",
    "与前一节类似，我们使用 `#pragma pack()` 让结构体紧凑排列，并定义 `ClientResponseType` 枚举，用于描述撮合引擎返回给客户端的回应类型：\n",
    "\n",
    "- [`#pragma pack(push, 1)`](./order_server/client_response.h#L11)\n",
    "- [`ClientResponseType`](./order_server/client_response.h#L12)\n",
    "\n",
    "`MEClientResponse` 结构包含以下关键信息：\n",
    "\n",
    "- `type_`：回应类型（`ClientResponseType`）\n",
    "- `client_id_`：目标客户（`ClientId`）\n",
    "- `ticker_id_`：相关交易标的（`TickerId`）\n",
    "- `client_order_id_`：客户端侧订单 ID（与请求中携带的一致）\n",
    "- `market_order_id_`：交易所/市场侧唯一订单 ID，贯穿所有市场参与者\n",
    "- `side_`：订单方向\n",
    "- `price_`：对应价格\n",
    "- `exec_qty_`：本次执行数量（仅执行事件使用，非累计值）\n",
    "- `leaves_qty_`：剩余待成交数量（订单簿中仍挂着的数量）\n",
    "\n",
    "同样提供 `toString()` 方法辅助日志输出：\n",
    "\n",
    "- [`MEClientResponse`](./order_server/client_response.h#L36)\n",
    "\n",
    "至此，客户端请求与响应的结构体定义完毕。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 定义 `MEMarketUpdate` 与 `MEMarketUpdateLFQueue`\n",
    "\n",
    "撮合引擎还需向行情发布器推送市场数据更新，因此定义 `MEMarketUpdate` 结构及 `MEMarketUpdateLFQueue`。相关代码位于 [`Chapter6/exchange/market_data/market_update.h`](./market_data/market_update.h)。\n",
    "\n",
    "与前文一样，我们使用 `#pragma pack()`，并定义 `MarketUpdateType` 枚举来描述市场更新动作（新增、修改、撤单、成交）：\n",
    "\n",
    "- [`MarketUpdateType`](./market_data/market_update.h#L12)\n",
    "\n",
    "`MEMarketUpdate` 结构包含：\n",
    "\n",
    "- `type_`：市场更新类型\n",
    "- `order_id_`：受影响的订单 ID\n",
    "- `ticker_id_`：对应标的\n",
    "- `side_`：订单方向\n",
    "- `price_`：价格\n",
    "- `qty_`：数量\n",
    "- `priority_`：订单在该价位 FIFO 队列中的排位\n",
    "\n",
    "同样提供 `toString()`：\n",
    "\n",
    "- [`MEMarketUpdate`](./market_data/market_update.h#L36)\n",
    "\n",
    "至此，我们已准备好撮合引擎在客户端交互与市场数据发布中所需的全部结构。下一步将构建限价订单簿所依赖的内部类型与数据结构。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 设计交易所订单簿 / Designing the exchange order book\n",
    "\n",
    "Designing the exchange order book\n",
    "In this section, we will define some building blocks that will be used to build, maintain, and update the limit order book in an efficient manner. Before we discuss each of the structures and objects we will need, we will present a diagram for you to build a visual understanding of the limit order book implementation.\n",
    "The limit order book is organized as a collection of buy orders (referred to as bids) and sell orders (referred to as asks). Orders that are entered at the same price are organized in the First In First Out (FIFO) order in our matching engine. We discussed these details in the Designing Our Trading Ecosystem chapter, in the Designing the C++ matching engine in a trading exchange section.\n",
    "For the order book we build inside the matching engine, we have a list of bid prices and ask prices that have active orders. Each price level is represented by the MEOrdersAtPrice struct, as shown in the following diagram. The bids are sorted from highest to lowest price level, and the asks are sorted from lowest to highest price level. Each MEOrdersAtPrice stores the individual orders from highest to lowest priority in a doubly linked list. Information for each individual order is contained in the MEOrder structs. We will track each price level in a hash map of type OrdersAtPriceHashMap, which is indexed by the price of that level. We will also track each MEOrder object by their market_order_id_ value in a hash map of type OrderHashMap. The diagram representing this design of our matching engine order book is presented as follows.\n",
    "\n",
    "Figure 6.1 – The design of the limit order book inside the matching engine\n",
    "\n",
    "<img src=\"./images/6.1.png\" alt=\"Figure 6.1 – The design of the limit order book inside the matching engine\" style=\"zoom:50%;\" />\n",
    "\n",
    "Now that we have discussed the overall design of the limit order book data structure and the components that make it up, we can start defining the basic structs we need to implement that design. In the next subsection, we will first design the basic blocks – the MEOrder structure to hold information for a single order.\n",
    "\n",
    "\n",
    "在本节中，我们将定义若干构建块，用于在撮合引擎内高效地构建、维护并更新限价订单簿。在逐一讨论所需的结构与对象之前，我们先用一幅示意图帮助你建立对限价订单簿实现方式的直观理解。\n",
    "\n",
    "限价订单簿由买单（买价，bids）和卖单（卖价，asks）两部分组成。在我们的撮合引擎里，同一价格下的订单会按照先进先出（FIFO）的原则组织。关于这些细节，我们已经在《设计我们的交易生态系统》一章中“设计交易所的 C++ 撮合引擎”一节讨论过。\n",
    "\n",
    "对于撮合引擎内部的订单簿，我们维护一个仍有挂单的买价列表和卖价列表。每个价格层级都由 `MEOrdersAtPrice` 结构表示，如下图所示。买价从高到低排序，卖价从低到高排序。每个 `MEOrdersAtPrice` 以双向链表存储该价位下按优先级从高到低排列的各个订单。单笔订单的信息保存在 `MEOrder` 结构中。我们通过以价格为键的哈希表 `OrdersAtPriceHashMap` 追踪每个价格层级，并通过以 `market_order_id_` 为键的哈希表 `OrderHashMap` 追踪每个 `MEOrder` 对象。下图展示了这一撮合引擎订单簿设计：\n",
    "\n",
    "[图 6.1 —— 撮合引擎内部限价订单簿的设计](./images/mermaid.md#L6.1)\n",
    "\n",
    "- **OrdersAtPriceHashMap**: 以价格为键的哈希表，指向不同价格级别的订单列表\n",
    "- **MEOrdersAtPrice**: 价格级别节点，通过PREV/NEXT形成双向链表\n",
    "- **MEOrder**: 具体订单，在每个价格级别内也形成双向链表\n",
    "- **OrderHashMap**: 以订单ID为键的哈希表，可快速查找订单\n",
    "- **Head of Bids/Asks**: 最优买/卖价的入口点\n",
    "\n",
    "现在我们已经介绍了限价订单簿数据结构的整体设计及其组成部分，接下来可以开始定义实现该设计所需的基本结构。在下一小节中，我们将首先设计最基础的积木——用于保存单笔订单信息的 `MEOrder` 结构。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 定义 `MEOrder`、`OrderHashMap` 与 `ClientOrderHashMap` 类型\n",
    "\n",
    "第一个结构体用于在订单簿中保存单笔限价订单的信息，命名为 `MEOrder`。相关代码如下，位于 GitHub 仓库的 [`Chapter6/matcher/me_order.h`](./matcher/me_order.h) 与 [`Chapter6/matcher/me_order.cpp`](./matcher/me_order.cpp)。\n",
    "\n",
    "`MEOrder` 结构体包含以下关键数据成员，用于记录一笔订单在限价订单簿中的属性：\n",
    "\n",
    "- `ticker_id_`：类型为 `TickerId`，表示该订单所属的交易品种。\n",
    "- `client_id_`：类型为 `ClientId`，表示持有该订单的市场参与者。\n",
    "- 两个 `OrderId`：`client_order_id_`（客户端下单时携带的订单号）与 `market_order_id_`（撮合引擎生成的、在所有客户端间唯一的订单号）。\n",
    "- `side_`：类型为 `Side`，表示这是买单还是卖单。\n",
    "- `price_`：类型为 `Price`，表示订单价格。\n",
    "- `qty_`：类型为 `Qty`，表示订单在订单簿中仍然有效的数量。\n",
    "- `priority_`：类型为 `Priority`，表示在同一方向与价格的订单队列中，该订单的精确排位。\n",
    "- `MEOrder` 结构体还包含两个指向其他 `MEOrder` 对象的指针。正如上一节所述，同一价位下的 `MEOrder` 对象会组成双向链表，在 `MEOrdersAtPrice` 结构体里按顺序维护。\n",
    "\n",
    "- [`MEOrder`](./matcher/me_order.h#L10)\n",
    "\n",
    "此外，我们使用 `OrderHashMap` 类型表示一个哈希表（通过 `std::array` 实现），键为 `OrderId`，值为 `MEOrder*`。同时定义 `ClientOrderHashMap`，它同样使用 `std::array` 实现，从 `ClientId` 映射到对应的 `OrderHashMap` 对象：\n",
    "\n",
    "- [`OrderHashMap`](./matcher/me_order.h#L34)\n",
    "\n",
    "`MEOrder` 结构体的 `toString()` 方法定义在 [`Chapter6/exchange/matcher/me_order.cpp`](./matcher/me_order.cpp) 文件中，内容非常简洁：\n",
    "\n",
    "- [`toString()`](./matcher/me_order.cpp)\n",
    "\n",
    "接下来，我们将构建其他用于容纳与管理订单对象的结构。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 定义 MEOrdersAtPrice 与 OrdersAtPriceHashMap 类型\n",
    "\n",
    "正如图 6.1 所示，我们需要另一个结构体来维护 `MEOrder` 对象列表，称为 `MEOrdersAtPrice`。下方代码展示了该结构，它用于保存所有以同一价格进入的订单，并按照 FIFO 优先级排序。为此，我们创建了一个指向 `MEOrder` 类型的指针 `first_me_order_`，表示该价位的首个订单，随后订单按 FIFO 顺序串接。\n",
    "\n",
    "`MEOrdersAtPrice` 结构体还包含两个指向其他 `MEOrdersAtPrice` 对象的指针：`prev_entry_`（前一个价位）与 `next_entry_`（后一个价位）。这是因为该结构本身是 `MEOrdersAtPrice` 节点组成的双向链表中的一部分；该双向链表在买卖两侧分别按照从最积极到最不积极的价格排序。该结构另外还包含 `side_`（`Side` 类型）与 `price_`（`Price` 类型）两个变量，分别表示该价位的方向与价格：\n",
    "\n",
    "- [`MEOrdersAtPrice`](./matcher/me_order.h#L37)\n",
    "\n",
    "我们添加一个默认构造函数，以及一个用于初始化该结构体对象的简单构造函数：\n",
    "\n",
    "- [`MEOrdersAtPrice()`](./matcher/me_order.h#L48)\n",
    "\n",
    "同时提供一个用于日志的简易 `toString()` 方法，如下所示：\n",
    "\n",
    "- [`MEOrdersAtPrice()`](./matcher/me_order.cpp#L4)\n",
    "\n",
    "`OrdersAtPriceHashMap` 类型表示一个哈希表，通过 `std::array` 实现，用于将 `Price` 映射到 `MEOrdersAtPrice*`：\n",
    "\n",
    "- [`OrdersAtPriceHashMap`](./matcher/me_order.cpp#L64)\n",
    "\n",
    "至此，我们完成了为撮合引擎与限价订单簿搭建基础类型、定义与结构体的准备工作。下一步，我们将继续了解撮合引擎框架如何构建。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 构建撮合引擎并交换外部数据 / Building the matching engine and exchanging external data\n",
    "\n",
    "在本节中，我们将搭建撮合引擎类的各个组成部分。处理客户端请求、构建与更新限价订单簿、生成订单响应与行情更新等大量工作，都将交由订单簿类完成——下一节会详细讨论该类。请回顾上一章《设计我们的交易生态系统》中“设计交易所的 C++ 撮合引擎”一节，以便重新熟悉我们在本节将要构建的组件以及背后的设计理念。为了便于参考，我们再次给出那一章中的示意图，展示撮合引擎的设计：\n",
    "\n",
    "<img src=\"./images/6.2.png\" alt=\"Figure 6.2 – The design of our matching engine component\" style=\"zoom:100%;\" />\n",
    "\n",
    "- [图 6.2 —— 我们的撮合引擎组件设计](../05/images/mermaid.md#L)\n",
    "\n",
    "撮合引擎以独立线程运行：它从 `ClientRequestLFQueue` 中获取订单请求，向 `ClientResponseLFQueue` 发布订单响应，并向 `MEMarketUpdateLFQueue` 发布行情更新。接下来，我们先声明并定义一些与构造、析构、线程管理及基础功能相关的代码。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 构建撮合引擎 / Building the matching engine\n",
    "\n",
    "`MatchingEngine` 类包含若干重要的数据成员：首先是一个 `OrderBookHashMap` 对象，用于追踪每个交易标的的限价订单簿。类中还持有以下对象的指针——`ClientRequestLFQueue`、`ClientResponseLFQueue` 与 `MEMarketUpdateLFQueue`，它们都会通过构造函数传入。接下来，我们首先声明并定义撮合引擎在构造、析构、线程管理和样板功能方面的代码。类中还会有一个布尔值 `run_` 用于跟踪线程状态，以及一个字符串 `time_str_` 和一个 `Logger` 对象用于输出日志。本节所用到的代码可在本书 GitHub 仓库的 [`Chapter6/exchange/matcher/matching_engine.h`](./matcher/matching_engine.h) 文件中找到。\n",
    "\n",
    "接着我们声明构造函数与析构函数，并添加 `start()` 与 `stop()` 方法，以分别启动和停止稍后要构建的撮合引擎主循环：\n",
    "\n",
    "- [`MatchingEngine`](./matcher/matching_engine.h#L12)\n",
    "\n",
    "我们像往常一样，删除默认构造、拷贝/移动构造以及赋值运算符，以避免出现意外的拷贝：\n",
    "\n",
    "- [`MatchingEngine() = delete;`](./matcher/matching_engine.h#73)\n",
    "\n",
    "最后，我们按照之前的讨论，为 `MatchingEngine` 类添加数据成员。`OrderBookHashMap` 类型的 `ticker_order_book_` 变量用于为每个品种存储 `MEOrderBook`。我们保存 `ClientRequestLFQueue`、`ClientResponseLFQueue` 和 `MEMarketUpdateLFQueue` 类型的指针，分别命名为 `incoming_requests_`、`outgoing_ogw_responses_` 和 `outgoing_md_updates_`，用于与其他线程通信。然后我们有布尔变量 `run_`，我们将其标记为 `volatile`，因为它会被不同的线程访问：\n",
    "\n",
    "- [`MatchingEngine`](./matcher/matching_engine.h#L83)\n",
    "\n",
    "> - **`volatile` 的作用**：告诉编译器该变量随时可能被外部（如硬件寄存器）修改，因此不要对其做寄存器缓存或相关优化。但是它并不提供同步语义，也不会禁止编译器、CPU 做重排序。\n",
    "> - **多线程可见性与原子性**：在并发场景下，要保证一个标志位在不同线程之间的可见性和原子性（以及可能需要的内存序约束），应该使用 `std::atomic<bool>`。`std::atomic` 才会确保每个线程看到的值是及时、可预测的，且读写操作具有原子性。\n",
    "\n",
    "现在让我们看看构造函数、析构函数以及 `start()` 方法的实现，`start()` 方法会创建并启动一个线程来执行 `run()` 方法（我们很快会看到）。这些代码位于 `Chapter6/exchange/matcher/matching_engine.cpp` 源文件中。\n",
    "\n",
    "构造函数本身很直接——它初始化内部数据成员，并为每个受支持的交易工具创建一个 `MEOrderBook` 实例：\n",
    "\n",
    "- [`MatchingEngine::MatchingEngine`](./matcher/matching_engine.cpp#L4)\n",
    "\n",
    "析构函数和构造函数正好相反，它会重置内部数据成员变量，并删除在构造函数中创建的 `MEOrderBook` 对象：\n",
    "\n",
    "- [`MatchingEngine::~MatchingEngine()`](./matcher/matching_engine.cpp#L13)\n",
    "\n",
    "`start()` 方法创建并启动一个新线程，并将其分配为执行 `MatchingEngine::run()` 方法。在此之前，它会启用 `run_` 标志，因为该标志控制着 `run()` 方法的执行：\n",
    "\n",
    "- [`MatchingEngine::start()`](./matcher/matching_engine.cpp#L29)\n",
    "\n",
    "`stop()` 方法只是简单地将 `run_` 标志设置为 `false`，这样就会导致 `run()` 方法退出其主循环，但这一点很快就会变得清晰：\n",
    "\n",
    "- [`MatchingEngine::stop()`](./matcher/matching_engine.cpp#L34)\n",
    "\n",
    "接下来，我们将研究撮合引擎如何消费订单请求并发布订单响应与行情更新的源代码。但首先，让我们展示撮合引擎线程执行的主 `run()` 循环。这段代码非常简单——它只是从 `incoming_requests_` 无锁队列中读取 `MEClientRequest` 对象，并将其转发到 `processClientRequest()` 方法。为此，它只需检查 `LFQueue::getNextToRead()` 方法，查看是否有可读条目，如果有，就将该条目中的对象转发处理，并使用 `LFQueue::updateReadIndex()` 来更新锁自由队列中的读取索引。这段代码位于 [`Chapter6/exchange/matcher/matching_engine.h`](./matcher/matching_engine.h) 源文件中：\n",
    "\n",
    "- [`run()`](./matcher/matching_engine.h#L59)\n",
    "\n",
    "现在，让我们来看看处理客户端请求的源代码。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 从订单网关队列读取与发布数据 / Consuming from and publishing to the order gateway queue\n",
    "\n",
    "首先，我们来看位于 `matching_engine.h` 头文件中 `MatchingEngine` 类的 `processClientRequest()` 实现。该实现只是检查 `MEClientRequest` 的类型，并将其转发到对应交易品种的限价订单簿。它通过访问 `ticker_order_book_` 容器，并使用 `MEClientRequest` 中的 `ticker_id_` 字段，找到该请求对应的正确订单簿实例：\n",
    "\n",
    "- [`processClientRequest`](./matcher/matching_engine.h#L24)\n",
    "\n",
    "对于尝试添加新订单的客户端请求（`ClientRequestType::NEW`），我们调用 `MEOrderBook::add()` 方法，让它处理该请求：\n",
    "\n",
    "- [`ClientRequestType::NEW`](./matcher/matching_engine.h#L27)\n",
    "\n",
    "同样地，尝试取消已有订单的客户端请求（`ClientRequestType::CANCEL`）会被转发给 `MEOrderBook::cancel()` 方法：\n",
    "\n",
    "- [`ClientRequestType::CANCEL`](./matcher/matching_engine.h#L33)\n",
    "\n",
    "我们还会在同一个类中定义一个方法，让限价订单簿可以通过 `MEClientResponse` 消息发布订单响应。这段代码只是将响应写入 `outgoing_ogw_responses_` 无锁队列，并推进写索引。它通过调用 `LFQueue::getNextToWriteTo()` 找到下一个可写入 `MEClientResponse` 消息的槽位，把数据移动到该位置，并调用 `LFQueue::updateWriteIndex()` 更新下一个写入索引：\n",
    "\n",
    "- [`sendClientResponse`](./matcher/matching_engine.h#L45)\n",
    "\n",
    "接下来，我们将查看与刚才类似的一些代码，不过它用于发布行情数据更新。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 发布到行情发布者队列 / Publishing to the market data publisher queue\n",
    "\n",
    "`Chapter6/exchange/matcher/matching_engine.h` 中的 `sendMarketUpdate()` 方法被限价订单簿用来通过 `MEMarketUpdate` 结构发布行情更新。它只是将数据写入 `outgoing_md_updates_` 无锁队列并推进写入指针。具体流程与之前完全相同：调用 `getNextToWriteTo()` 方法，向返回的槽位写入 `MEMarketUpdate` 消息，再通过 `updateWriteIndex()` 更新下一次写入索引：\n",
    "\n",
    "- [`sendMarketUpdate()`](./matcher/matching_engine.h#L52)\n",
    "\n",
    "至此，本节内容结束，我们已经完成了撮合引擎的实现。在下一小节中，我们会把这些部分整合到交易所可执行文件中（限价订单簿的实现除外，因为那是本章最后会讨论的部分）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 构建交易所应用二进制 / Building the exchange application binary\n",
    "\n",
    "现在我们可以构建交易所二进制程序。我们将实例化撮合引擎对象所需的三个无锁队列，分别用于订单请求、订单响应和行情更新。我们还会创建 `MatchingEngine` 对象并启动线程，然后该二进制程序就会一直休眠。由于应用程序会进入无限循环，我们还会为其安装一个信号处理程序，用于捕获外部信号并优雅退出。请注意，随着我们在本书的后续章节中构建交易所侧的订单服务器和行情发布组件，这段代码还会有所扩展，并需要在此处加入这些组件。该应用程序的代码位于本书 GitHub 仓库的 [`Chapter6/exchange/exchange_main.cpp`](./main.cpp) 中。下面我们将分解该源文件，并理解其中每个代码块。\n",
    "\n",
    "首先，我们添加一些变量，它们将分别作为 `Logger` 对象和 `MatchingEngine` 对象的指针。同时，我们还会添加一个 `signal_handler()` 方法，用于在关闭交易所应用时被调用。该信号处理函数会简单地删除这些对象并退出：\n",
    "\n",
    "- [`signal_handler()`](./main.cpp#L8)\n",
    "\n",
    "`main()` 方法目前还很简单，直到我们在下一章加入其他组件。它使用 `std::signal()` 例程安装 `signal_handler()` 方法，以捕获外部的 `SIGINT` 信号。`SIGINT` 信号的值为 2，当在 Linux 中按下 `Ctrl + C` 或发送 `kill -2 PID` 到某个进程 ID（PID）时，该信号会被发送到正在运行的进程。这是优雅终止进程的常见方式。接着，它初始化 `ClientRequestLFQueue` 变量 `client_requests` 和 `ClientResponseLFQueue` 变量 `client_responses`，它们的大小都为 `ME_MAX_CLIENT_UPDATES`。我们还初始化 `MEMarketUpdateLFQueue` 类型的无锁队列变量 `market_updates`，其容量为 `ME_MAX_MARKET_UPDATES`。`main()` 方法还通过创建一个 `Logger` 类实例来初始化 `logger` 变量：\n",
    "\n",
    "- [`main`](./main.cpp#L20)\n",
    "\n",
    "最后，`main()` 方法用我们创建的 `MatchingEngine` 类实例初始化 `matching_engine` 变量，并传入上面代码块中准备好的三个无锁队列。然后调用 `start()` 方法，以便主撮合引擎线程开始执行。此时，`main()` 方法的工作就完成了，于是它进入一个无限循环，在其中大部分时间都在休眠，并等待一个将终止该进程的外部信号：\n",
    "\n",
    "- [`matching_engine = new Exchange::MatchingEngine`](./main.cpp#L34)\n",
    "\n",
    "了便于构建主二进制程序，我们提供了一个脚本 `Chapter6/build.sh`，它使用 CMake 和 Ninja 来构建该二进制。你需要将脚本中的路径更新为你系统中的正确二进制文件，或者根据喜好使用其他构建系统。下一节将介绍如何运行这个 `exchange_main` 应用程序。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 运行交易所应用二进制 / Running the exchange application binary\n",
    "\n",
    "此时，运行 `exchange_main` 应用程序只需直接调用该二进制文件，如下代码块所示。同时，我们也展示终端上应当出现的输出："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd ../../run && ./matching_engine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如先前所述，可以通过向该进程发送 `SIGINT` 信号来停止它。此时，它会生成三个日志文件，类似于下列示例。不过请注意，由于目前我们只构建了撮合引擎组件（而尚未构建完整交易生态系统所需的其他组件），这些日志中暂时没有有趣的内容。在下一章《与市场参与者通信》的结尾，我们会再次运行此应用，并加入更多组件，此时输出会稍微更有意思："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 构建订单簿并撮合订单 / Building the order book and matching orders\n",
    "\n",
    "最后这一节实现订单簿功能。请记住，订单簿负责处理撮合引擎转发过来的客户端订单请求。它会检查订单请求类型，更新订单簿，为客户端生成订单响应，并为公共行情数据流生成行情更新。撮合引擎中限价订单簿的全部代码都在 `me_order_book.h` 和 `me_order_book.cpp` 源文件中，保存在本书 GitHub 仓库的 `Chapter6/exchange/matcher/` 目录内。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 构建内部数据结构 / Building the internal data structures\n",
    "\n",
    "首先，我们将为限价订单簿声明数据成员。我们之前在图 6.1 中展示了构成限价订单簿的数据结构示意图。限价订单簿包含以下重要数据成员：\n",
    "\n",
    "- 一个指向 MatchingEngine 父类的 `matching_engine_` 指针变量，订单簿通过它向父对象发布订单响应和市场数据更新。\n",
    "- `ClientOrderHashMap` 变量 `cid_oid_to_order_`，按 `ClientId` 键跟踪 `OrderHashMap` 对象。提醒一下，`OrderHashMap` 通过 `OrderId` 键跟踪 `MEOrder` 对象。\n",
    "- `MEOrdersAtPrice` 对象的内存池变量 `orders_at_price_pool_`，用于创建新对象并回收失效对象。\n",
    "- 买单（`bids_by_price_`）和卖单（`asks_by_price_`）双向链表的头指针，因为我们以 `MEOrdersAtPrice` 对象列表的形式按价格层级跟踪订单。\n",
    "- 一个哈希映射 `OrdersAtPriceHashMap`，以价格作为键来跟踪价格层级的 `MEOrdersAtPrice` 对象。\n",
    "- `MEOrder` 对象的内存池 `order_pool_`，用于创建和回收 `MEOrder` 对象，从而避免动态内存分配。\n",
    "- 一些次要成员，例如该订单簿对应标的的 `TickerId`、用于跟踪下一个市场数据订单 ID 的 `OrderId`、一个 `MEClientResponse` 变量（`client_response_`）、一个 `MEMarketUpdate` 对象（`market_update_`）、用于记录时间的字符串以及用于日志记录的 `Logger` 对象。\n",
    "\n",
    "首先，我们包含一些依赖的头文件，并前向声明 `MatchingEngine` 类，因为我们将引用该类型但尚未完全定义它：\n",
    "\n",
    "- [`MatchingEngine`](./matcher/me_order_book.h#L14)\n",
    "\n",
    "接下来，我们按照之前讨论的内容定义数据成员变量：\n",
    "\n",
    "- [`MEOrderBook`](./matcher/me_order_book.h#L39)\n",
    "\n",
    "在此，我们还将定义之前提到的 `OrderBookHashMap` 类型，它是按 `TickerId` 索引的 `MEOrderBook` 对象的 `std::array`：\n",
    "\n",
    "- [`OrderBookHashMap`](./matcher/me_order_book.h#L199)\n",
    "\n",
    "接下来，让我们展示构造函数和析构函数的简单实现，以及默认构造函数和赋值运算符的样板代码：\n",
    "\n",
    "- [`MEOrderBook::MEOrderBook`](./matcher/me_order_book.cpp#L6)\n",
    "- [`MEOrderBook::~MEOrderBook()`](./matcher/me_order_book.cpp#L11)\n",
    "\n",
    "然后，我们在大多数类中加入样板代码，以防止 `MEOrderBook` 对象被意外复制或赋值：\n",
    "\n",
    "- [`MEOrderBook() = delete;`](./matcher/me_order_book.h#L29)\n",
    "\n",
    "在继续实现订单簿将执行的各种操作之前，先介绍几个简单的方法，用于生成新的市场订单 ID、将 `Price` 转换为 `OrdersAtPriceHashMap` 中的索引，以及在给定 `Price` 的情况下访问 `OrdersAtPriceHashMap` 的 `price_orders_at_price_` 映射：\n",
    "\n",
    "- [`MEOrderBook`](./matcher/me_order_book.h#L16)\n",
    "\n",
    "`generateNewMarketOrderId()` 方法非常基础；它返回 `next_market_order_id_` 的值，并在下一次调用时递增：\n",
    "\n",
    "- [`generateNewMarketOrderId()`](./matcher/me_order_book.h#L63)\n",
    "\n",
    "`priceToIndex()` 方法将 `Price` 参数转换为 0 到 `ME_MAX_PRICE_LEVELS-1` 之间的索引，然后用于索引价格层级的 `std::array`：\n",
    "\n",
    "- [`priceToIndex()`](./matcher/me_order_book.h#L67)\n",
    "\n",
    "最后，`getOrdersAtPrice()` 工具方法通过调用 `priceToIndex()` 方法将提供的 `Price` 转换为索引，从而在 `price_orders_at_price_` 的 `std::array` 中返回 `MEOrdersAtPrice` 对象：\n",
    "\n",
    "- [`getOrdersAtPrice()`](./matcher/me_order_book.h#L71)\n",
    "\n",
    "接下来的几个小节将详细介绍处理新订单请求、取消请求，以及撮合跨越对手方静态订单的激进订单的重要操作。我们还将生成并发布订单响应和市场数据更新返回给撮合引擎。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 处理新的被动订单/ Handling new passive orders\n",
    "\n",
    "在订单簿中，我们首先需要执行的重要任务是处理希望进入市场的新订单的客户端请求。我们将实现 `MEOrderBook::add()` 方法，这是撮合引擎首先调用的方法。它生成并发送 `MEClientResponse`，接受新订单，并将其发送到撮合引擎（由撮合引擎发送给提交新订单的客户端）。然后，它还会检查这个新订单是否跨越了对手方已有的静态订单，并且是否能够完全或部分成交，这通过调用 `checkForMatch()` 方法实现。如果新订单没有成交，或者部分成交后仍有剩余数量，`MEOrder` 就会被添加到订单簿中。在这种情况下，它还会生成用于公共市场数据馈送的 `MEMarketUpdate`，并将其返回给撮合引擎（由市场数据发布组件发布）。\n",
    "\n",
    "我们会在本节稍后讨论 `getNextPriority()`、`checkForMatch()` 和 `addOrder()` 方法，但先看看 `MEOrderBook::add()` 方法：\n",
    "\n",
    "- [`MEOrderBook::add()`](./matcher/me_order_book.cpp#81)\n",
    "\n",
    "它首先生成 `new_market_order_id_`，用于 `MEClientResponse` 和 `MEMarketUpdate`。它用此次请求的属性更新成员变量 `client_response_`，并调用 `MatchingEngine::sendClientResponse()` 方法，把该响应发布回撮合引擎：\n",
    "\n",
    "- [`MEOrderBook::add()`](./matcher/me_order_book.cpp#82)\n",
    "\n",
    "接下来，`MEOrderBook::add()` 方法调用 `MEOrderBook::checkForMatch()` 方法，该方法根据刚进入的客户端请求检查当前订单簿状态，判断是否可以进行部分或全部成交。稍后我们将构建的 `checkForMatch()` 方法会返回匹配事件后剩余的数量（如果有）。对于完全未成交的订单，返回的 `leaves_qty` 等于原始订单数量。对于部分成交的订单，是匹配后剩余的数量。对于完全成交的订单，该方法会返回 0，并赋值给 `leaves_qty`。目前，我们先调用它：\n",
    "\n",
    "- [`MEOrderBook::add()`](./matcher/me_order_book.cpp#86)\n",
    "\n",
    "如果匹配事件后仍然有剩余数量，我们需要生成一个市场数据更新，表示这个新订单将挂入订单簿。为此，`MEOrderBook::add()` 方法通过调用 `MEOrderBook::getNextPriority()` 方法获取该订单正确的优先级。它从 `order_pool_` 内存池分配一个新的 `MEOrder` 对象，并赋予其属性。然后调用 `MEOrderBook::addOrder()` 方法，将其以正确的价格层级和优先级添加到 `MEOrdersAtPrice` 数据结构中。最后，它将市场更新的值填充到 `market_update_` 对象中，并调用 `MatchingEngine::sendMarketUpdate()` 方法将其发布到撮合引擎：\n",
    "\n",
    "- [`MEOrderBook::add()`](./matcher/me_order_book.cpp#88)\n",
    "\n",
    "`getNextPriority()` 方法相当直接。如果某个价格层级已经存在，则返回该价位最后一个订单的优先级再加一。如果该价位还没有价格层级，则返回 `1`，表示该价位的第一笔订单：\n",
    "\n",
    "- [`getNextPriority()`](./matcher/me_order_book.h#L143)\n",
    "\n",
    "接下来，我们将详细说明如何向限价订单簿添加新订单。该方法在 `MEOrdersAtPrice` 条目中将传入的 `MEOrder` 对象追加到最后。如果 `MEOrdersAtPrice` 条目不存在（新价格层级），则先从 `orders_at_price_pool_` 分配一个新条目，初始化后调用 `addOrdersAtPrice()` 方法，然后再追加订单。此外，它还使用按 `ClientId` 和 `OrderId` 映射到 `MEOrder` 对象的 `ClientOrderHashMap` 跟踪订单：\n",
    "\n",
    "- [`addOrder()`](./matcher/me_order_book.h#L178)\n",
    "\n",
    "首先，我们尝试通过调用 `getOrdersAtPrice()` 方法检查并获取现有的 `MEOrdersAtPrice`，并保存到 `orders_at_price` 变量。然后检查是否存在有效的 `MEOrdersAtPrice`，即该订单的价格和方向对应的价格层级是否已经存在。如果不存在，这是该价位形成的第一个订单，则我们从 `orders_at_price_pool_` 分配一个新的 `MEOrdersAtPrice`，初始化后调用 `addOrdersAtPrice()` 方法：\n",
    "\n",
    "- [`addOrder()`](./matcher/me_order_book.h#L179)\n",
    "\n",
    "如果价格层级存在，我们将新订单追加到 `MEOrdersAtPrice` 的 `first_me_order_` 可达的 `MEOrder` 双向循环链表的最末尾。接着我们更新要添加的 `MEOrder` 的 `prev_order_` 和 `next_order_` 指针以及链表末尾元素，然后再将该 `MEOrder` 对象追加进去：\n",
    "\n",
    "- [`addOrder()`](./matcher/me_order_book.h#L186)\n",
    "\n",
    "最后，我们将该 `MEOrder` 指针添加到 `cid_oid_to_order_` 容器中，该容器是一个 `std::array` 嵌套 `std::array`，先用订单的 `client_id_` 索引，再用 `client_order_id_` 索引：\n",
    "\n",
    "- [`addOrder()`](./matcher/me_order_book.h#L195)\n",
    "\n",
    "最后，为了完成关于向订单簿添加新订单的讨论，我们需要实现 `addOrdersAtPrice()` 方法，以将新的价格层级添加到订单簿中。该方法首先将新的 `MEOrdersAtPrice` 条目添加到 `OrdersAtPriceHashMap price_orders_at_price_` 中。然后，它会遍历买盘或卖盘的价格层级，从最优价格到最差价格，找到这条价格层级的正确插入位置。注意，该实现通过遍历该方向的 `MEOrdersAtPrice` 双向链表实现。也可以实现另一种方法，即遍历 `price_orders_at_price_` 哈希映射来寻找正确位置。两种实现都可行且性能不同，这取决于价格层级数量以及相邻价格之间的距离。我们将在本书结尾的《优化 C++ 系统性能》章节再次讨论这一主题。`addOrdersAtPrice()` 方法的第一项任务是将新的 `MEOrdersAtPrice` 以价格为键插入 `price_orders_at_price_` 哈希映射：\n",
    "\n",
    "- [`addOrdersAtPrice()`](./matcher/me_order_book.h#L75)\n",
    "\n",
    "然后，我们需要把它插入到按价格排序的买盘或卖盘中。我们先将最优价格层级赋值给 `best_orders_by_price` 变量，它指向按价格排序的买盘或卖盘的开头：\n",
    "\n",
    "- [`addOrdersAtPrice()`](./matcher/me_order_book.h#L78)\n",
    "\n",
    "我们需要处理一个特殊情况，即买盘或卖盘为空——也就是说，订单簿的某一侧为空。在这种情况下，我们将 `bids_by_price_` 或 `asks_by_price_` 设置为该侧价格层级排序列表的头节点：\n",
    "\n",
    "- [`addOrdersAtPrice()`](./matcher/me_order_book.h#L79)\n",
    "\n",
    "否则，我们需要在该双向链表中找到正确的价格层级。为此，我们遍历买盘或卖盘，直到找到新价格层级应该插入在之前还是之后的位置。我们用 `target` 变量记录新价格层级前后的位置，并用布尔变量 `add_after` 跟踪是否需要插入在 `target` 之后：\n",
    "\n",
    "- [`addOrdersAtPrice()`](./matcher/me_order_book.h#L82)\n",
    "\n",
    "一旦我们找到了新 `MEOrdersAtPrice` 条目的正确位置，就通过更新目标 `MEOrdersAtPrice` 结构以及新结构中的 `prev_entry_` 或 `next_entry_` 指针，来完成新价格层级的追加，如下所示\n",
    "\n",
    "- [`addOrdersAtPrice()`](./matcher/me_order_book.h#L98)\n",
    "\n",
    "最后，如果我们在现有价格层级前添加了新价格层级，需要检查是否更改了 `bids_by_price_` 或 `asks_by_price_` 变量。记住，这些变量分别跟踪买盘或卖盘的起始位置——也就是最高买价和最低卖价。如果新价格层级成为新的最优买价或卖价，我们就分别更新 `bids_by_price_` 或 `asks_by_price_` 变量：\n",
    "\n",
    "- [`addOrdersAtPrice()`](./matcher/me_order_book.h#L112)\n",
    "\n",
    "接下来，我们将讨论处理订单取消请求的源代码。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 处理订单取消请求 / Handling order cancellation requests\n",
    "\n",
    "处理订单取消请求的代码由撮合引擎转发而来。首先，它检查取消请求是否有效，即 `ClientId` 是否有效，以及取消请求中的 `OrderId` 是否对应于订单簿中的活动订单。如果订单不可取消，它会生成并发布一个 `MEClientResponse` 消息，表明取消请求被拒绝，返回给撮合引擎。如果订单可以取消，它会生成 `MEClientResponse`，表明取消成功，并调用 `removeOrder()` 方法从限价订单簿中删除该订单。我们将在下一个方法之后讨论 `removeOrder()` 的细节。\n",
    "\n",
    "我们将用一个布尔变量 `is_cancelable` 来跟踪是否成功找到并取消了客户端的订单。如果 `client_id` 大于最大可能的 `ClientId`，则无法取消该订单。如果 `client_id` 有效，我们会在 `cid_oid_to_order_` 中用提供的 `client_id` 和 `order_id` 进行检查。如果没有有效的订单存在，就确认该订单不可取消：\n",
    "\n",
    "- [`MEOrderBook::cancel`](./matcher/me_order_book.cpp#L100)\n",
    "\n",
    "如果我们确定不能取消该订单，就生成一个 `ClientResponseType::CANCEL_REJECTED` 类型的 `MEClientResponse` 消息，通知撮合引擎：\n",
    "\n",
    "- [`MEOrderBook::cancel`](./matcher/me_order_book.cpp#L109)\n",
    "\n",
    "如果订单可以成功取消，我们就更新成员变量 `client_response_` 和 `market_update_` 中的属性。然后调用 `removeOrder()` 方法更新订单簿并删除该订单。最后，我们调用 `sendMarketUpdate()` 方法将市场更新发送至撮合引擎，并调用 `sendClientResponse()` 方法将客户端响应发送至撮合引擎：\n",
    "\n",
    "- [`MEOrderBook::cancel`](./matcher/me_order_book.cpp#L112)\n",
    "\n",
    "接下来，让我们实现 `removeOrder()` 方法。它首先找到要移除的订单所属的 `MEOrdersAtPrice`，然后在其中的订单列表里找到并删除 `MEOrder`。如果被移除的订单是该价格层级中的唯一订单，该方法还会调用 `removeOrdersAtPrice()`，因为删除后该价格层级不再存在。最后，它将该 `MEOrder` 在 `cid_oid_to_order_` 哈希映射中的条目清除，并把被释放的 `MEOrder` 对象归还给 `order_pool_` 内存池：\n",
    "\n",
    "- [`removeOrder()`](./matcher/me_order_book.h#L156)\n",
    "\n",
    "为了完成处理订单取消请求的讨论，我们将实现 `removeOrdersAtPrice()` 方法。该方法会在买盘或卖盘的 `MEOrdersAtPrice` 双向链表中找到并删除对应的条目。如果被删除的价格层级是该方向唯一的 `MEOrdersAtPrice` 条目，它会将该方向链表的头指针设为 `nullptr`，表示该侧为空。最后，该方法会将该价格在 `price_orders_at_price_` 哈希映射中的条目清除，并把释放的 `MEOrdersAtPrice` 归还给 `orders_at_price_pool_` 内存池：\n",
    "\n",
    "- [`removeOrdersAtPrice()`](./matcher/me_order_book.h#L121)\n",
    "\n",
    "最后一个需要处理的重要操作是撮合跨越对手静态订单的激进订单，并更新订单簿。在下一部分，我们将实现该操作。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 撮合积极订单并更新订单簿 / Matching aggressive orders and updating the order book\n",
    "\n",
    "在本小节中，我们将通过展示 `MEOrderBook::checkForMatch()` 方法来实现限价订单簿中的撮合功能，我们之前已经遇到过它。图 6.3 展示了一个假设的限价订单簿状态下会发生什么。在这里展示的是卖盘状态，静态卖价由 `MEOrdersAtPrice` 表示，按顺序为 117、118、119 等。在最优卖价 117 处，展示了两个 `MEOrder` 对象，第一个的优先级为 11，市场订单 ID 为 1200，数量为 20。紧随其后的 FIFO 队列中的 `MEOrder`，优先级为 13，市场订单 ID 为 1400，数量为 10。在这种情况下，一个数量为 25、价格为 117 的新买单（用蓝色表示）会先与市场订单 ID 为 1200 的订单（黄色表示）完全成交。然后，它会用剩余数量 5 去部分成交市场订单 ID 为 1400 的订单（洋红色表示），至此撮合事件结束。这些步骤在随后的算法中给出。\n",
    "\n",
    "<img src=\"./images/6.3.png\" alt=\"Figure 6.3 – An example of a matching event in the limit order book\" style=\"zoom:100%;\" />\n",
    "\n",
    "图 6.3 – 限价订单簿中一次撮合事件示例\n",
    "\n",
    "这个方法遍历订单簿另一侧的 `MEOrdersAtPrice` 对象。它会从最优到最差的价格层级逐一遍历，并对每个价格层级中的 `MEOrder` 对象按 FIFO 顺序（从最先到最后）进行撮合。它通过调用 `match()` 方法，持续用新订单去匹配另一侧的静态订单，从最优价格逐渐到最差价格，并在价格层级内按先后顺序处理。该方法在新激进订单剩余数量耗尽、剩余价格层级不再与新订单价格交叉，或该方向订单簿为空时停止，并返回新订单的剩余未匹配数量：\n",
    "\n",
    "- [`MEOrderBook::checkForMatch`](./matcher/me_order_book.cpp#154)\n",
    "\n",
    "如果方向是买单（`Side::BUY`），我们会遍历从最低价到最高价排列的所有卖盘价格层级，从 `asks_by_price_` 开始。在 `asks_by_price_` 层级，我们从 `MEOrder` 类型指针 `first_me_order_` 开始按 FIFO 顺序，顺次遍历每个订单。对于每个能够与新的激进订单匹配的订单，我们调用 `MEOrder::match()` 方法执行实际撮合。我们一直执行，直到没有剩余数量 `leaves_qty`，或者 `asks_by_price_` 为 `nullptr`（表示该方向为空），或者剩余的价格层级无法再与新订单匹配：\n",
    "\n",
    "- [`MEOrderBook::checkForMatch`](./matcher/me_order_book.cpp#L57)\n",
    "\n",
    "如果新订单的方向是卖单，我们执行与上述相同的逻辑，只是遍历从最高价到最低价排列的买盘价格层级 `bids_by_price_`，如下所示：\n",
    "\n",
    "- [`MEOrderBook::checkForMatch`](./matcher/me_order_book.cpp#L67)\n",
    "\n",
    "`match()` 方法在新激进订单与订单簿中另一侧的静态订单成交时被调用。它计算成交数量，即新订单数量和静态订单数量的最小值。它会用该成交数量减去激进订单的剩余数量以及静态订单的剩余数量。它会生成两个成交订单响应并发送给撮合引擎：一个给提交激进订单的客户，另一个给静态订单被执行的客户。它还会创建并发布一个 `MarketUpdateType::TRADE` 的市场更新，通知参与者关于成交的情况。最后，它会检查此次交易是否完全执行了静态订单。如果完全成交，它会生成另一个 `MarketUpdateType::CANCEL` 的市场更新，通知参与者该静态订单已被移除；如果只是部分成交，则生成 `MarketUpdateType::MODIFY`，提供该限价订单剩余的数量。\n",
    "\n",
    "这意味着，即使参与者选择忽略市场数据流中的成交消息，他们仍能准确构建和维护限价订单簿。理论上我们可以省略额外的取消或修改市场更新，但这要求下游市场数据消费者应用成交消息更新他们的订单簿。`MEOrderBook::match()` 方法接受一些参数来识别客户信息，但关键参数是 `MEOrder` 指针 `itr` 和 `Qty` 指针 `leaves_qty`。`MEOrder` 指针表示订单簿中与新订单匹配的订单，而 `Qty` 表示新订单的剩余数量。因为我们会在该方法中直接修改它们，所以通过指针传递以便调用方能看到变化：\n",
    "\n",
    "- [`MEOrderBook::checkForMatch`](./matcher/me_order_book.cpp#L22)\n",
    "\n",
    "我们将 `fill_qty` 计算为订单簿中静态订单数量与新订单数量的最小值。然后使用 `fill_qty` 分别减少激进订单的剩余数量 `leaves_qty` 和 `MEOrder` 对象中的 `qty_` 成员：\n",
    "\n",
    "- [`MEOrderBook::checkForMatch`](./matcher/me_order_book.cpp#L23)\n",
    "\n",
    "我们生成一个 `ClientResponseType::FILLED` 类型的客户端响应，发送给提交新订单的客户，并通过 `sendClientResponse()` 方法发送至撮合引擎：\n",
    "\n",
    "- [`MEOrderBook::checkForMatch`](./matcher/me_order_book.cpp#L30)\n",
    "\n",
    "我们也为订单簿中被匹配的客户端生成第二个 `ClientResponseType::FILLED` 响应：\n",
    "\n",
    "- [`MEOrderBook::checkForMatch`](./matcher/me_order_book.cpp#L34)\n",
    "\n",
    "我们还生成一个 `MarketUpdateType::TRADE` 的市场更新，并通过 `sendMarketUpdate()` 发布，通知参与者成交交易及 `fill_qty`：\n",
    "\n",
    "- [`MEOrderBook::checkForMatch`](./matcher/me_order_book.cpp#L38)\n",
    "\n",
    "最后，我们为订单簿中的静态订单生成市场更新。如果该订单仍有剩余数量，则生成 `MarketUpdateType::MODIFY` 消息，附上新的剩余数量。如果该订单被完全执行，则生成 `MarketUpdateType::CANCEL` 更新，发布后还会调用 `MEOrderBook::removeOrder()` 方法将该 `MEOrder` 从订单簿中移除：\n",
    "\n",
    "- [`MEOrderBook::checkForMatch`](./matcher/me_order_book.cpp#L41)\n",
    "\n",
    "至此，我们完成了关于处理客户端订单请求、在撮合引擎中更新限价订单簿，以及生成并发布订单响应和市场更新的讨论。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 总结\n",
    "\n",
    "本章我们开始实现电子交易生态系统的 C++ 版本。首先构建了交易所撮合引擎，它负责接收来自交易所基础设施中订单服务器组件的订单请求并返回响应，同时生成并向市场数据发布器组件推送市场数据更新。\n",
    "\n",
    "我们先在撮合引擎和限价订单簿中声明了一些假设，并定义了几种基础的 POD（Plain Old Data）结构，分别用于封装限价订单簿中的单个订单、订单服务器发出的单个订单请求、发送回订单服务器的订单响应，以及单条市场数据更新。我们演示了如何使用无锁队列在撮合引擎、订单服务器和市场数据发布器之间传递订单请求、订单响应和市场数据更新。为构建限价订单簿，我们还定义了若干哈希表，用于按订单 ID 跟踪订单，并在 MEOrdersAtPrice 结构中串联同价位的订单。这些价位本身通过双向链表和按价格索引的哈希表进行维护。\n",
    "\n",
    "随后，我们构建了撮合引擎组件。该组件以独立线程运行，从订单服务器消费更新，并向订单服务器和市场数据发布器发布响应和市场数据更新。我们还构建了电子交易所的主应用程序二进制文件，将在下一章进一步增强。\n",
    "\n",
    "最后，我们详细介绍了构建和更新限价订单簿数据结构的机制，讨论了处理新订单请求和订单取消请求的流程，并实现了撮合引擎的核心功能——将新的主动订单与价格交叉的已有被动订单进行匹配。撮合事件会为参与者生成私有执行消息，并在公共市场数据推送中产生成交消息以及订单删除或修改信息。\n",
    "\n",
    "下一章将实现市场数据发布器组件，它负责消费撮合引擎生成的市场数据更新并对外发布。此外，我们还将构建位于电子交易所内、负责与各个市场参与者的订单网关通信并在撮合引擎之间转发请求与响应的订单服务器组件。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "C++17",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
